package com.ywgt;

/**
 * 动态规划
 */
public class Dynamic {
    public static void main(String[] args) {
        int [] w={1,4,3};//每个物品的重量
        int [] val={1500,3000,3000}; //每个物品的价值
        int m=4;//背包最大容量
        int n=val.length; //物品的个数
        //v[i][j]表示在第i个物品中，能够装入容量为j的背包的最大值
        int[][] v=new int[n+1][m+1];
        int[][] path=new int[n+1][m+1];

        for (int i = 1; i < v.length; i++) {
            for (int j = 1; j < v[i].length; j++) {
                if(w[i-1]>j){ //如果当前物资的重量大于背包剩余容量，那么将上个单元格的价值复制过来
                    v[i][j]=v[i-1][j];
                }else {
                    //v[i-1][j] 上一个单元格的价值
                    // val[i-1]当前商品的价值
                    // [i-1]为上次（前一行）装入的商品；j-w[i]为当前容量减去当前商品的重量
                    //意思为上次在装入容量为j-w[i]时的价值 比如最后一次加入的重量为3的商品，而背包容量为4，那么还有一个
                    //剩余的容量，则会用这个物品的价值加上上次容量为【1】时的价值和上一行的单元格比较，如果比他大，那就取最大值
                    i=i;
                    int k=j-w[i-1];
                    int l=v[i-1][j-w[i-1]];
                    if(v[i-1][j]<val[i-1]+v[i-1][j-w[i-1]]){
                        v[i][j]=val[i-1]+v[i-1][j-w[i-1]];
                        path[i][j]=1;
                    }else {
                        v[i][j]=v[i-1][j];
                    }
                }
            }
        }

        for (int i = 0; i < v.length; i++) {
            for (int j = 0; j < v[i].length; j++) {
                System.out.print("\t"+v[i][j]);
            }
            System.out.println();
        }
        System.out.println("----------->");
        for (int j = 0; j < path.length; j++) {
            for (int k = 0; k < path[j].length; k++) {
                System.out.print("\t"+path[j][k]);
            }
            System.out.println();
        }
        System.out.println("----------->");
        int x=path.length-1;
        int y=path[0].length-1;
        while(x>0&&y>0){
            if(path[x][y]==1){
                System.out.println("放入了第"+x+"商品"); //先找到最后一件加入的商品，就是没有进行上一行复制的最后一次添加的物品的下标x
                y-=w[x-1]; //x-1             //然后用y也就是当时加进去时的重量减去加入物品的重量，找到上一次添加物品时的位置
            }
            x--;
        }

    }



}
